#include <bits/stdc++.h>

using namespace std;
const int maxn=12;
struct node
{
    int lchild,rchild;
} nodes[maxn];
bool notRoot[maxn]={false};
int n4,num4=0;
void printNode(int id)
{
    printf("%d",id);
    ++num4;
    if (num4<n4)
    {
        printf(" ");
    }else
    {
        printf("\n");
    }
}
void inOrder(int root)
{
    if (root==-1)
    {
        return;
    }
    inOrder(nodes[root].lchild);
    printNode(root);
    inOrder(nodes[root].rchild);
}
void BFS(int root)
{
    queue<int> q;
    q.push(root);
    while (!q.empty())
    {
        int now=q.front();
        q.pop();
        printNode(now);
        if (nodes[now].lchild!=-1)
        {
            q.push(nodes[now].lchild);
        }
        if (nodes[now].rchild!=-1)
        {
            q.push(nodes[now].rchild);
        }
    }
}
void postOrder(int root)
{
    if (root==-1)
    {
        return;
    }
    postOrder(nodes[root].lchild);
    postOrder(nodes[root].rchild);
    swap(nodes[root].lchild,nodes[root].rchild);
}
int char2num(char c)
{
    if (c=='-')
    {
        return -1;
    }
    else
    {
        notRoot[c-'0']=true;
        return c-'0';
    }
}
int findRoot()
{
    for (int i=0;i<n4 ;++i )
    {
        if (notRoot[i]==false)
        {
            return i;
        }
    }
}
int main_1102()
{
    char lchild,rchild;
    scanf("%d",&n4);
    for (int i=0;i<n4 ;++i )
    {
        scanf("%*c%c %c",&lchild,&rchild);
        nodes[i].lchild=char2num(lchild);
        nodes[i].rchild=char2num(rchild);
    }
    int root =findRoot();
    postOrder(root);
    BFS(root);
    num4=0;
    inOrder(root);
    return 0;
}
